1190. The Smallest Label a Route Can Read

Every cell of an r by c grid holds an uppercase letter and every cell is free. A route goes from the top-left cell to the bottom-right cell using only steps DOWN and RIGHT, and READS the string formed by the letters of the cells it stands on, in order, including both ends. Every route therefore reads a string of exactly r + c - 1 letters.

Print the lexicographically smallest string any route reads, and then how many routes read it.

3 3 smallest string ABAZZ, read by 4 of the 6 routes ABZ ABAZZ BAZ -> 4 ZZZ

## What most people try first

Enumerate the routes, as in #1184, keep the smallest string and count the ties. That is the right answer and the wrong method, and here the gap is not a constant factor. The number of routes is C(r + c - 2, r - 1), which at the stated limit of 20 by 20 is C(38, 19), or 35345263800. A machine examining ten million routes a second needs about an hour. The intended solution does about four hundred steps.

## The observation that collapses it

Number the ANTI-DIAGONALS by i + j. A down step and a right step both increase i + j by exactly one, so after s moves every route is somewhere on anti-diagonal s, whatever route it took. Routes therefore move in lockstep: they all read their first letter from diagonal 0, their second from diagonal 1, and so on.

That means the smallest string can be chosen one letter at a time, greedily, and the greedy choice is safe. Among all the cells reachable on diagonal s by a route that has read the best possible prefix, take the smallest letter. Any route whose prefix is already worse can never recover, because the strings all have the same length and lexicographic order is decided by the first difference.

## The method

Keep a map from cell to the NUMBER of routes that reach it having read the best prefix so far. Advance it one diagonal at a time:

reach = { top-left cell : 1 }, label = letter at the top-left repeat r + c - 2 times: next = {} for each cell in reach, for each of its down and right neighbours inside the grid: next[neighbour] += reach[cell] best = the smallest letter among the cells of next drop from next every cell whose letter is not best label = label + best reach = next answer = label, and reach at the bottom-right cell

Only cells on one diagonal are ever live, so the whole thing is O(r * c).

## Why it is correct

Two claims, and the counting one is the one people get wrong.

For the string: by induction on s, reach holds exactly the cells on diagonal s that some route reaches having read the smallest possible first s + 1 letters. The step takes every extension of those routes, picks the smallest next letter, and discards the rest. Discarding is safe because all routes have equal length, so a route with a larger letter at position s + 1 reads a larger string no matter what follows.

For the count: the number stored at a cell is the number of best-prefix routes reaching it, and a route reaching a neighbour is an extension of exactly one route reaching exactly one of that neighbour's two predecessors. So summing the predecessors counts every such route once and none twice. The final diagonal is the single bottom-right cell, so the number stored there is the answer. Note that it is NOT the number of routes in the grid: in the worked example 4 of the 6 routes read the smallest string and 2 do not.

## Overflow

This is where this topic genuinely overflows, and the tag on the 20 by 20 test is not decoration. If every letter is the same, every route reads the same string and the count is the total number of routes, C(38, 19), which is 35345263800. That is more than sixteen times the 2147483647 a signed 32 bit integer holds, so a 32 bit accumulator wraps and prints a wrong, often negative, number. Use a 64 bit type.

In a language whose only numeric type is a double, 35345263800 is exact, because a double carries 53 bits of integer precision and this needs 36. The trap there is different and it is real: any bitwise operator truncates its operands to 32 bits first, so a single | 0 or >>> 0 anywhere near the accumulator destroys the answer.

## Cost

O(r * c) cells examined once each, against C(r + c - 2, r - 1) routes for the enumeration, which is 400 against 35345263800 at the stated limit.

Constraints - `1 ≤ r, c ≤ 20` - Every cell holds an uppercase English letter. - Every cell is free; there are no blocked cells.